<!DOCTYPE html>
<html>
<head>
    <meta charset="utf-8" >

<title>每日一题20201118（31. 下一个排列） | 小克的blog</title>

<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1, user-scalable=no">

<link rel="stylesheet" href="https://use.fontawesome.com/releases/v5.7.2/css/all.css" integrity="sha384-fnmOCqbTlWIlj8LyTjo7mOUStjsKC4pOpQbqyi7RrhN7udi9RwhKkMHpvLbHG9Sr" crossorigin="anonymous">
<link rel="shortcut icon" href="https://woodywrx.gitee.io/blog/favicon.ico?v=1615823433634">
<link rel="stylesheet" href="https://woodywrx.gitee.io/blog/styles/main.css">



<link rel="stylesheet" href="https://unpkg.com/aos@next/dist/aos.css" />
<script src="https://cdn.jsdelivr.net/npm/vue/dist/vue.js"></script>



    <meta name="description" content="31. 下一个排列

思路
首先说一下什么是字典序，把1 2 3当作a b c的话，abc有6种排列顺序。
abc acb bac bca cab cba

上图就是字典序，题目的要求狠简单： 找到下一个字典序，如果没有的话，则输出最小的序..."/>
    <meta name="keywords" content="leetcode"/>
</head>
<body>

<div id="app" class="main">

    <div class="sidebar" :class="{ 'full-height': menuVisible }">
  <div class="top-container" data-aos="fade-right">
    <div class="top-header-container">
      <a class="site-title-container" href="https://woodywrx.gitee.io/blog">
        <img src="https://woodywrx.gitee.io/blog/images/avatar.png?v=1615823433634" class="site-logo">
        <h1 class="site-title">小克的blog</h1>
      </a>
      <div class="menu-btn" @click="menuVisible = !menuVisible">
        <div class="line"></div>
      </div>
    </div>
    <div>
      
        
          <a href="https://woodywrx.gitee.io/blog" class="site-nav">
            首页
          </a>
        
      
        
          <a href="https://woodywrx.gitee.io/blog/tags" class="site-nav">
            标签
          </a>
        
      
        
          <a href="https://woodywrx.gitee.io/blog/post/about" class="site-nav">
            关于
          </a>
        
      
    </div>
  </div>
  <div class="bottom-container" data-aos="flip-up" data-aos-offset="0">
    <div class="social-container">
      
        
      
        
      
        
      
        
      
        
      
    </div>
    <div class="site-description">
      欢迎来到我的小窝~这里不仅有博客，也有日记。
    </div>
    <div class="site-footer">
      wuranxu's blog | <a class="rss" href="https://woodywrx.gitee.io/blog/atom.xml" target="_blank">RSS</a>
    </div>
  </div>
</div>


    <div class="main-container">
        <div class="content-container" data-aos="fade-up">
            <div class="post-detail">
                <h2 class="post-title">每日一题20201118（31. 下一个排列）</h2>
                <div class="post-date">2020-11-18 14:28:47</div>
                
                <div class="post-content" v-pre>
                    <h4 id="31-下一个排列"><a href="https://leetcode-cn.com/problems/next-permutation/">31. 下一个排列</a></h4>
<figure data-type="image" tabindex="1"><img src="https://tva1.sinaimg.cn/large/0081Kckwgy1gktavcwbfsj30u00zedjn.jpg" alt="image-20201118141644763" loading="lazy"></figure>
<h4 id="思路">思路</h4>
<p>首先说一下什么是字典序，把1 2 3当作a b c的话，abc有6种排列顺序。</p>
<pre><code>abc acb bac bca cab cba
</code></pre>
<p>上图就是字典序，题目的要求狠简单： 找到下一个字典序，如果没有的话，则输出最小的序号。</p>
<p>首先明确一下，没有下一个序列的情况，那么就是大的全部在前面，所以只需要反转数组就行，就可以回到最小的序列。</p>
<pre><code>再看有下一个排序的情况，我们需要先从右侧找到一个比最右边数字小的数.

然后再和右边第一个大于这个数的数进行交换，以571632为例子：

第一个小于右侧数字的数是1，第一个大于1的数字是2，交换之后:

572631, 由于之前确定的，是通过升序找到的1，所以还需要反转2后面的数字: 572136 就是最终结果了！

正好可以和上面反转的一起处理。
</code></pre>
<pre><code class="language-Python">class Solution:
    def nextPermutation(self, nums: List[int]) -&gt; None:
        &quot;&quot;&quot;
        Do not return anything, modify nums in-place instead.
        &quot;&quot;&quot;
        # 左侧的第一个非升序数字，这里也可以len(nums)-2
        j = len(nums)-1
        while j-1 &gt;= 0:
            if nums[j] &gt; nums[j-1]:
                break
            j -= 1
        # 如果j-1&gt;=0说明找到了这个数字，否则说明数组
        # 是降序排列的
        if j-1 &gt;= 0:
            right = len(nums)-1
            # 找到右边第一个大于nums[j-1]的数字
            while right &gt; j-1 and nums[right] &lt;= nums[j-1]:
                right -= 1
            # 交换他们
            nums[j-1], nums[right] = nums[right], nums[j-1]
            self.reverse(nums, j, len(nums)-1)
        else:
            self.reverse(nums, 0, len(nums)-1)
            
    # 反转数组
    def reverse(self, nums, i, j):
        while i &lt; j:
            nums[i], nums[j] = nums[j], nums[i]
            i += 1
            j -= 1
        return nums

</code></pre>
<figure data-type="image" tabindex="2"><img src="https://tva1.sinaimg.cn/large/0081Kckwgy1gktb6z1z4hj30xs0e03zz.jpg" alt="image-20201118142757008" loading="lazy"></figure>

                </div>
                
                    <div class="tag-container">
                        
                            <a href="https://woodywrx.gitee.io/blog/vp-bY7-nD/" class="tag">
                                leetcode
                            </a>
                        
                    </div>
                

                
                    <div class="next-post">
                        <div class="next">下一篇</div>
                        <a href="https://woodywrx.gitee.io/blog/post/mei-ri-er-ti-2020111734-zai-pai-xu-shu-zu-zhong-cha-zhao-yuan-su-de-di-yi-ge-he-zui-hou-yi-ge-wei-zhi/">
                            <h3 class="post-title">
                                每日二题20201117（34. 在排序数组中查找元素的第一个和最后一个位置）
                            </h3>
                        </a>
                    </div>
                
                
                    <span id="/blog/post/mei-ri-yi-ti-2020111831-xia-yi-ge-pai-lie/"
                          class="leancloud_visitors" data-flag-title="每日一题20201118（31. 下一个排列）">
                <em class="post-meta-item-text">阅读量 </em>
                <i class="leancloud-visitors-count">0</i>
            </span>
                
                
                    

	<div id="vcomments" style="width: 100%;max-width:1000%;padding:2.5%"></div>



                

            </div>

        </div>
    </div>
</div>

<script src="https://unpkg.com/aos@next/dist/aos.js"></script>
<script type="application/javascript">

AOS.init();

var app = new Vue({
  el: '#app',
  data: {
    menuVisible: false,
  },
})

</script>






<script src='https://cdn.jsdelivr.net/npm/valine/dist/Valine.min.js'></script>
<script>
    new Valine({
        el: '#vcomments',
        appId: 'fT8wvEVNtx1cOcCQEs7rVwnV-gzGzoHsz',
        appKey: 'xV6aDHKSkLfP7u0cBRIzpmcy',
        avatar: '',
        pageSize: 5,
        recordIp: true,
        placeholder: 'Just Go Go',
        visitor: true,
    });
</script>
<script async src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>
</body>
</html>
